# matrix = [[1,2,3],[4,5,6],[7,8,9]]
matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
# matrix=[[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,16]]
direction={0:[0,1],1:[1,0],2:[0,-1],3:[-1,0]}
def dfs(matrix,state,x,y,res,rank):
    if len(res)==len(matrix[0])*len(matrix):
        #全部的元素都遍历到了，就退出递归
        return None
    for k in range(4):
        x_i,y_j=x+direction[(rank+k)%4][0],y+direction[(rank+k)%4][1]
        if x_i>=0 and x_i<len(matrix) and y_j>=0 and y_j<len(matrix[0]) and not state[x_i][y_j]:
            state[x_i][y_j]=True
            res.append(matrix[x_i][y_j])
            dfs(matrix,state,x_i,y_j,res,(rank+k)%4)
    # #先往右走：右的优先级一定要在下前面
    # x_i,y_j=x,y+1
    # if x_i>=0 and x_i<len(matrix) and y_j>=0 and y_j<len(matrix[0]) and not state[x_i][y_j]:
    #     state[x_i][y_j]=True
    #     res.append(matrix[x_i][y_j])
    #     dfs(matrix,state,x_i,y_j,res)
    # x_i,y_j=x+1,y
    # #下
    # if x_i>=0 and x_i<len(matrix) and y_j>=0 and y_j<len(matrix[0]) and not state[x_i][y_j]:
    #     state[x_i][y_j]=True
    #     res.append(matrix[x_i][y_j])
    #     dfs(matrix,state,x_i,y_j,res)
    # #左
    # x_i,y_j=x,y-1
    # if x_i>=0 and x_i<len(matrix) and y_j>=0 and y_j<len(matrix[0]) and not state[x_i][y_j]:
    #     state[x_i][y_j]=True
    #     res.append(matrix[x_i][y_j])
    #     dfs(matrix,state,x_i,y_j,res)
    # x_i,y_j=x-1,y
    # #上
    # if x_i>=0 and x_i<len(matrix) and y_j>=0 and y_j<len(matrix[0]) and not state[x_i][y_j]:
    #     state[x_i][y_j]=True
    #     res.append(matrix[x_i][y_j])
    #     dfs(matrix,state,x_i,y_j,res)

def spiralOrder(matrix):
    state=[[False for _ in range(len(matrix[0]))] for _ in range(len(matrix))]
    state[0][0]=True
    res=[matrix[0][0]]
    rank=0
    dfs(matrix,state,0,0,res,rank)
    return res
print(spiralOrder(matrix))
